package hdoj;

import java.util.Scanner;

public class DigitDpHDU3555 {

	//1 ~ 2^ 63 - 1
	
	long[][] dp = new long[20][10];
	long[] base = new long[20];
	
	public void initWrong(){
		for(int i = 1; i < dp.length; i++){
			for(int j = 0; j < 10; j++){
				//枚举第i - 1位
				for (int k = 0; k < 10; k++) {
					if(k == 9 && j == 4){
						dp[i][j] += base[i - 1];
					}else{
						dp[i][j] += dp[i - 1][k];
					}
				}
			}
		}
//		for(int i = 0; i < dp.length; i++){
//			for(int j = 0; j < 10; j++){
//				System.out.print(dp[i][j] + " ");
//			}
//			System.out.println();
//			if(i > 5){
//				break;
//			}
//		}
	}
	
	public long solveWrong(long n){
		if(n <= 0){
			return 0;
		}
		long ans = 0;
		int length = 0;
		int[] digits = new int[20];	//表示n从右到左第i位是几
		while(n != 0){
			digits[++length] = (int) (n % 10);
			n /= 10;
		}
		// System.out.println("length: " + length);
		//用来判断是否相等的
		for(int i = length; i > 0; i--){
			//枚举这一位的取值
			//由于我们是判断的含有49的，如果首位为4，次高位为9，低位为1，那么由于我们取得条件是小于4，所以会导致漏掉
			// 490、491 
			//因为90、91都不含有49，所以我们自然而然的漏掉了，这样写或许适合统计不含有子串的值(比如HDU2089)
			//但是不适合这里
			for(int j = 0; j < digits[i]; j++){
				ans += dp[i - 1][j];
			}
		}
		return ans;
	}
	
	
	int[] digits = new int[20];	//表示n从右到左第i位是几
	
	public void init(){
		for(int i = 0; i < dp.length; i++){
			for(int j = 0; j < 10; j++){
				dp[i][j] = -1;
			}
		}
	}
	
	public long solve(long n){
		if(n <= 0){
			return 0;
		}
		int length = 0;
		long temp = n;
		for(int i = 0; i < digits.length; i++){
			digits[i] = 0;
		}
		while(n != 0){
			digits[++length] = (int) (n % 10);
			n /= 10;
		}
		return dfs(length, 0, 0, true, temp);
	}
	
	//k表示是否包含49
	public long dfs(int length, int digit, int k, boolean flag, long n){
		if(length <= 0){
			return (k == 1) ? 1 : 0;
		}
		if(!flag && dp[length][digit] != -1){
			return dp[length][digit];
		}
		int end = flag ? digits[length] : 9;
		long ans = 0;
		for(int i = 0; i <= end; i++){
			if (digit == 4 && i == 9) {
	            ans += flag ? n % base[length - 1] + 1 : base[length - 1];
	            // System.out.println("length: " + length + " n % base[length - 1]: " + (n % base[length - 1]));
	        } else {  
	            ans += dfs(length - 1, i, k, flag && end == i, n);  
	        }  
		}
		if(!flag){
			dp[length][digit] = ans;
		}
		return ans;
	}
	
	
	public static void main(String[] args) {
		DigitDpHDU3555 object = new DigitDpHDU3555();
		object.getRes();
	}

	private void getRes() {
		Scanner scanner = new Scanner(System.in);
		base[0] = 1;
		for(int i = 1; i < base.length; i++){
			base[i] = base[i - 1] * 10;
		}
		init();
		int testCase = scanner.nextInt();
		long number;
		for(int i = 1; i<= testCase; i++){
			number = scanner.nextLong();
			System.out.println(solve(number));
		}
		scanner.close();
	}
}
